package gold.vo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/5/27.
 */
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x) {
        val = x;
    }

    TreeNode() {
    }

    /**
     * 创建tree的工具之源
     *
     * @param order
     * @return
     */
    public static TreeNode createTree(String order) {
        if (order.startsWith("[")) order = order.substring(1, order.length() - 1);
        List<String> levelList = Arrays.asList(order.split(","));

        if (levelList == null || levelList.isEmpty() || levelList.get(0).equals("null")) {
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(levelList.get(0)));
        Deque<TreeNode> preLayer = new LinkedList<>();
        Deque<TreeNode> curLayer = new LinkedList<>();
        int curLayerSize = 2;

        TreeNode curNode;
        preLayer.addLast(root);

        int currentIdx = 1;
        int len = levelList.size();
        while (currentIdx < len) {
            curLayerSize = preLayer.size() * 2;
            TreeNode father = preLayer.pollFirst();
            int nextFatherFlag = 0;
            for (int i = 0; i < curLayerSize && currentIdx + i < len; i++) {
                String curNodeVal = levelList.get(currentIdx + i);
                if ("null".equals(curNodeVal)) curNode = null;
                else curNode = new TreeNode(Integer.parseInt(curNodeVal));

                if (i % 2 == 0) father.left = curNode;
                else father.right = curNode;

                if (null != curNode) curLayer.addLast(curNode);
                if (++nextFatherFlag > 1) {
                    nextFatherFlag = 0;
                    father = preLayer.pollFirst();
                }
            }

            preLayer = curLayer;
            curLayer = new LinkedList<>();
            currentIdx += curLayerSize;
        }

        return root;
    }


    public static TreeNode createTree(String order, String mode) {
        List<String> levelList = getRawValue(order);

        if (levelList.get(0).equals(".")) {
            return null;
        }

        int len = levelList.size();
        int current = 0;
        TreeNode[] nodeArray = new TreeNode[levelList.size()];
        TreeNode curNode;
        while (current < len) {
            if (!".".equals(levelList.get(current)))
                curNode = new TreeNode(Integer.valueOf(levelList.get(current)));
            else
                curNode = null;

            if (current > 0) {
                int parentIdx = (current - 1) >> 1;
                if (current % 2 != 0) //left
                    nodeArray[parentIdx].left = curNode;
                else //right
                    nodeArray[parentIdx].right = curNode;
            }

            nodeArray[current] = curNode;
            ++current;
        }
        return nodeArray[0];
    }

    public static List<String> getRawValue(String order) {
        List<String> valList = new ArrayList<>();
        for (int i = 0; i < order.length(); i++) {
            char ch = order.charAt(i);
            if (' ' == ch) {
                StringBuilder tempBuilder = new StringBuilder();
                while (++i < order.length() && order.charAt(i) != ' ') {
                    tempBuilder.append(String.valueOf(order.charAt(i)));
                }
                valList.add(tempBuilder.toString());
            } else {
                valList.add(String.valueOf(ch));
            }
        }

        return valList;
    }

    public static void main(String[] args) {
        System.out.println(createTree("123...4"));
    }
}

